- Title
- On the Stanley–Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
- Creator
- Albert, M. H.; Elder, Murray; Rechnitzer, A.; Westcott, P.; Zabrocki, M.
- Relation
- Advances in Applied Mathematics Vol. 36, Issue 2, p. 96-105
- Publisher Link
- http://dx.doi.org/10.1016/j.aam.2005.05.007
- Publisher
- Academic Press
- Resource Type
- journal article
- Date
- 2006
- Description
- We show that the Stanley–Wilf limit for the class of 4231-avoiding permutations is at least by 9.47. This bound shows that this class has the largest such limit among all classes of permutations avoiding a single permutation of length 4 and refutes the conjecture that the Stanley–Wilf limit of a class of permutations avoiding a single permutation of length k cannot exceed (k−1)2. The result is established by constructing a sequence of finite automata that accept subclasses of the class of 4231-avoiding permutations and analysing their transition matrices.
- Subject
- permutation classes; Automata
- Identifier
- http://hdl.handle.net/1959.13/928094
- Identifier
- uon:10341
- Identifier
- ISSN:0196-8858
- Language
- eng
- Full Text
- Reviewed
- Hits: 3653
- Visitors: 4098
- Downloads: 534
Thumbnail | File | Description | Size | Format | |||
---|---|---|---|---|---|---|---|
View Details Download | SOURCE1 | Author final version | 119 KB | Adobe Acrobat PDF | View Details Download |